Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants. The method automatically generates a sequence of primal and dual feasible solutions to the original convex problem, making optimality certification easy. We establish theoretical properties of the nonconvex formulation, showing that it is (almost) free of spurious local minima and has the same global optimum as the convex problem. We modify projected gradient descent to avoid spurious local minimizers so it always converges to the global minimizer.

Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants. The method automatically generates a sequence of primal and dual feasible solutions to the original convex problem, making optimality certification easy.

Additional Feedback: Update after rebuttal After reading the rebuttal, I am happy with the answers regarding PDHG, and explanations about the proof for backtracking/momentum variants of the method. I find the approach promising. However, I think the work needs improvements in terms of presentation, which, I suggest the authors to consider when revising the paper. Especially the introduction of the idea can be made more friendly for the readers, with more explanations. I suggest the authors to also consider the minor questions in my review that are not mentioned in the rebuttal.

The paper considers structured convex optimization where constraints are given in a stage-wise manner. The paper studies a non-convex reformulation for this problem and proposes new algorithms to ensure convergence to global minimizers for both non-degenerate and degenerate cases. The reformulation is proven effective in theory and experiments. The author feedback phase has clarified several aspects, resulting in a consensus on weak acceptance. We hope the detailed feedback with improvement suggestions from the 4 reviews will be implemented for the camera ready version, in particular about the clarity and readability of the paper.

Convex optimization problems with staged structure appear in several contexts, including optimal control, verification of deep neural networks, and isotonic regression. Off-the-shelf solvers can solve these problems but may scale poorly. We develop a nonconvex reformulation designed to exploit this staged structure. Our reformulation has only simple bound constraints, enabling solution via projected gradient methods and their accelerated variants. The method automatically generates a sequence of primal and dual feasible solutions to the original convex problem, making optimality certification easy.